10995. Квадраты и кубы

 

Выпишем в ряд квадраты и кубы натуральных чисел: 1, 4, 8, 9, ....

Для заданного значения n посчитайте количество выписанных чисел от 1 до n. Иными словами, найдите количество таких x, что x является квадратом или кубом натурального числа (или и квадратом и кубом одновременно).

 

Вход. В первой строке записано количество тестов t.

В каждой из следующих t строк записано одно натуральное число n (1 ≤ n ≤ 109).

 

Выход. Для каждого теста выведите ответ – количество чисел от 1 до n, принадлежащих списку.

 

Пример входа

Пример выхода

5

1

10

25

1000000

987654321

1

4

6

1090

32390

 

 

РЕШЕНИЕ

бинарный поиск

 

Анализ алгоритма

Сгенерируем все квадраты и кубы чисел от 1 до 109 и занесем их во множество s. Повторы чисел будут уничтожены. Скопируем множество в массив v (он уже будет отсортирован, так как множество s упорядочено).

Далее для каждого входного числа n при помощи бинарного поиска находим количество квадратов и кубов, не больших n. Для этого по верхней границе (upper_bound) ищем положение числа n в массиве v. Найденная позиция и будет ответом.

 

Пример

Сгенерируем квадраты и кубы чисел от 1 до 100 включительно.

 

Выполним запрос для n = 30. Имеется в точности pos = 7 искомых чисел в промежутке от 1 до 30. Напомним, что индексация в массиве v начинается с 0.

 

Реализация алгоритма

Сгенерируем все квадраты и кубы чисел от 1 до 109 и занесем их во множество s. Если число является одновременно и квадратом и кубом (например, 64), оно будет храниться во множестве только один раз.

 

for (i = 1; i * i <= 1000000000; i++)

  s.insert(i * i);

for (i = 1; i * i * i <= 1000000000; i++)

  s.insert(i * i * i);

 

Перенесем множество в массив v. Поскольку множество s отсортировано, то и вектор v будет отсортирован.

 

v = vector<int>(s.begin(), s.end());

 

Последовательно обрабатываем tests тестов.

 

scanf("%d", &tests);

while (tests--)

{

  scanf("%d", &n);

 

При помощи бинарного поиска по верхней границе находим такой наименьший индекс pos, что все квадраты и кубы чисел, не больших n, расположены в индексах от 0 до pos – 1. Таким образом количество выписанных чисел от 1 до n равно pos.

 

  res = upper_bound(v.begin(), v.end(), n) - v.begin();

  printf("%d\n", res);

}